﻿\section{Циклы: несколько итераторов}
\label{loop_iterators}

Часто, у цикла только один итератор, но в итоговом коде их может быть несколько.

Вот очень простой пример:

\lstinputlisting[style=customc]{\CURPATH/iterators_RU.c}

Здесь два умножения на каждой итерации, а это дорогая операция.

Сможем ли мы соптимизировать это как-то?
Да, если мы заметим, что индексы обоих массивов перескакивают на места, рассчитать которые мы
можем легко и без умножения.

\subsection{Три итератора}

\lstinputlisting[caption=\Optimizing MSVC 2013 x64,style=customasmx86]{\CURPATH/MSVC_2013_x64_Ox_RU.asm}

Теперь здесь три итератора: переменная \IT{cnt} и два индекса, они увеличиваются на 12 и 28 на каждой
итерации, указывая на новые элементы массивов.

Мы можем переписать этот код на \CCpp:

\lstinputlisting[style=customc]{\CURPATH/iterators3_RU.c}

Так что, ценой модификации трех итераторов на каждой итерации вместо одного, 
мы избавлены от двух операций умножения.

\subsection{Два итератора}

GCC 4.9 сделал еще больше, оставив только 2 итератора:

\lstinputlisting[caption=\Optimizing GCC 4.9 x64,style=customasmx86]{\CURPATH/GCC491_x64_O3_RU.asm}

Здесь больше нет переменной-\IT{счетчика}: GCC рассудил, что она не нужна.

Последний элемент массива \IT{a2} вычисляется перед началом цикла (а это просто: $cnt*7$),
и при помощи этого цикл останавливается: просто исполняйте его пока второй индекс не сравняется
с предварительно вычисленным значением.

Об умножении используя сдвиги/сложения/вычитания, читайте здесь:
 
\myref{multiplication_using_shifts_adds_subs}.

Этот код можно переписать на \CCpp вот так:

\lstinputlisting[style=customc]{\CURPATH/iterators2_RU.c}

GCC (Linaro) 4.9 для ARM64 делает тоже самое, только предварительно вычисляет последний индекс массива \IT{a1} вместо
\IT{a2}, а это, конечно, имеет тот же эффект:

\lstinputlisting[caption=\Optimizing GCC (Linaro) 4.9 ARM64,label=GCC_no_number_sign,style=customasmARM]{\CURPATH/ARM64_GCC_49_O3_RU.s}

% FIXME1 -> post-increment

GCC 4.4.5 для MIPS делает то же самое:

\lstinputlisting[caption=\Optimizing GCC 4.4.5 для MIPS (IDA),style=customasmMIPS]{\CURPATH/MIPS_O3_IDA_RU.lst}

\subsection{Случай Intel C++ 2011}
\myindex{\CompilerAnomaly}
\label{loops_iterators_loop_anomaly}

Оптимизации компилятора могут быть очень странными, но, тем не менее, корректными.

Вот что делает Intel C++ 2011:

\lstinputlisting[caption=\Optimizing Intel C++ 2011 x64,style=customasmx86]{\CURPATH/intel_2011_x64_Ox.asm}

В начале, принимаются какие-то решения, затем исполняется одна из процедур.

Видимо, это проверка, не пересекаются ли массивы.

Это хорошо известный способ оптимизации процедур копирования блоков в памяти.

Но копирующие процедуры одинаковые!
Видимо, это ошибка оптимизатора Intel C++, который, тем не менее, генерирует работоспособный код.

Мы намеренно изучаем примеры такого кода в этой книге чтобы читатель мог понимать, что результаты работы
компилятором иногда бывают крайне странными, но корректными, потому что когда компилятор тестировали, 
тесты прошли нормально.

